{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Eliminate Maximum Number of Monsters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: eliminateMaximum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #消灭怪物的最大数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你正在玩一款电子游戏，在游戏中你需要保护城市免受怪物侵袭。给定一个 <strong>下标从 0 开始</strong> 且大小为 <code>n</code> 的整数数组 <code>dist</code> ，其中 <code>dist[i]</code> 是第 <code>i</code> 个怪物与城市的 <strong>初始距离</strong>（单位：米）。</p>\n",
    "\n",
    "<p>怪物以 <strong>恒定</strong> 的速度走向城市。每个怪物的速度都以一个长度为 <code>n</code> 的整数数组 <code>speed</code> 表示，其中 <code>speed[i]</code> 是第 <code>i</code> 个怪物的速度（单位：千米/分）。</p>\n",
    "\n",
    "<p>你有一种武器，一旦充满电，就可以消灭 <strong>一个</strong> 怪物。但是，武器需要 <strong>一分钟</strong> 才能充电。武器在游戏开始时是充满电的状态，怪物从 <strong>第 0 分钟</strong> 时开始移动。</p>\n",
    "\n",
    "<p>一旦任一怪物到达城市，你就输掉了这场游戏。如果某个怪物 <strong>恰好</strong>&nbsp;在某一分钟开始时到达城市（距离表示为0），这也会被视为<strong> 输掉</strong>&nbsp;游戏，在你可以使用武器之前，游戏就会结束。</p>\n",
    "\n",
    "<p>返回在你输掉游戏前可以消灭的怪物的 <strong>最大</strong> 数量。如果你可以在所有怪物到达城市前将它们全部消灭，返回&nbsp; <code>n</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dist = [1,3,4], speed = [1,1,1]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "第 0 分钟开始时，怪物的距离是 [1,3,4]，你消灭了第一个怪物。\n",
    "第 1 分钟开始时，怪物的距离是 [X,2,3]，你消灭了第二个怪物。\n",
    "第 3 分钟开始时，怪物的距离是 [X,X,2]，你消灭了第三个怪物。\n",
    "所有 3 个怪物都可以被消灭。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dist = [1,1,2,3], speed = [1,1,1,1]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "第 0 分钟开始时，怪物的距离是 [1,1,2,3]，你消灭了第一个怪物。\n",
    "第 1 分钟开始时，怪物的距离是 [X,0,1,2]，所以你输掉了游戏。\n",
    "你只能消灭 1 个怪物。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>dist = [3,2,4], speed = [5,3,2]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "第 0 分钟开始时，怪物的距离是 [3,2,4]，你消灭了第一个怪物。\n",
    "第 1 分钟开始时，怪物的距离是 [X,0,2]，你输掉了游戏。 \n",
    "你只能消灭 1 个怪物。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == dist.length == speed.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= dist[i], speed[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [eliminate-maximum-number-of-monsters](https://leetcode.cn/problems/eliminate-maximum-number-of-monsters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [eliminate-maximum-number-of-monsters](https://leetcode.cn/problems/eliminate-maximum-number-of-monsters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,4]\\n[1,1,1]', '[1,1,2,3]\\n[1,1,1,1]', '[3,2,4]\\n[5,3,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        for i in range(n):\n",
    "            t = dist[i]//speed[i]\n",
    "            t = t if dist[i]%speed[i]==0 else t+1\n",
    "            dist[i]=t\n",
    "        dist.sort(reverse=True)\n",
    "        for i in range(n):\n",
    "            if dist[-1]<=i:\n",
    "                return i\n",
    "            dist.pop()\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        time = []\n",
    "        for d, s in zip(dist, speed):\n",
    "            a, r = divmod(d, s)\n",
    "            t = a + 1*(r!=0)\n",
    "            time.append(t)\n",
    "            \n",
    "        time.sort()\n",
    "        time = [t-i for i, t in enumerate(time)]\n",
    "        for i in range(n):\n",
    "            if time[i] == 0:\n",
    "                return i\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n=len(dist)\n",
    "        times_died=[math.ceil(dist[i]/speed[i]) for i in range(n)]\n",
    "        times_died.sort()\n",
    "        ans=[i for i in range(n)]\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            if times_died[i]>ans[i]:\n",
    "                res+=1  \n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        n = len(dist)\n",
    "        time = SortedList()\n",
    "        for i in range(n):\n",
    "            time.add(dist[i] / speed[i])\n",
    "        print(time)\n",
    "        t = 0\n",
    "        cnt = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if t < time[i]:\n",
    "                cnt += 1\n",
    "                t += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        time = []\n",
    "        for i in range(len(dist)):\n",
    "            time.append(math.ceil(dist[i] / speed[i]))\n",
    "        d = Counter(time)\n",
    "        shot = 0\n",
    "        for i in sorted(d.keys()):\n",
    "            if shot + d[i] > i:\n",
    "                return i\n",
    "            else:\n",
    "                shot += d[i]\n",
    "        return len(dist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        times = [math.ceil(dist[i]/speed[i]) for i in range(len(dist))]\n",
    "\n",
    "        t_c = defaultdict(int)\n",
    "        for t in times:\n",
    "            t_c[t] += 1\n",
    "\n",
    "        keys = sorted(t_c.keys())\n",
    "        index = 0\n",
    "        result = 0\n",
    "        for i in range(max(keys)):\n",
    "            if index >= len(keys):\n",
    "                break\n",
    "            if keys[index] <= i:\n",
    "                break\n",
    "\n",
    "            result += 1\n",
    "\n",
    "            if t_c[keys[index]] <= 1:\n",
    "                index += 1\n",
    "            else:\n",
    "                t_c[keys[index]] -= 1\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "from math import ceil\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        time = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            time[ceil(dist[i] / speed[i])] += 1\n",
    "        arrival = []\n",
    "        for key in time:\n",
    "            arrival.append((key, time[key]))\n",
    "        arrival.sort()\n",
    "        total = 0\n",
    "        for key,value in arrival:\n",
    "            if total + value > key:\n",
    "                return key\n",
    "            else:\n",
    "                total += value\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        total = sorted(range(n), key=lambda i: dist[i] / speed[i])\n",
    "        n = len(total)\n",
    "        second = 0\n",
    "        for i in total:\n",
    "            if dist[i] - speed[i] * second <= 0: break\n",
    "            second += 1\n",
    "            \n",
    "        return second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        lo, hi = 1, len(dist)\n",
    "        n = len(dist)\n",
    "        tmp = []\n",
    "        for i in range(n):\n",
    "            tmp.append(math.ceil(dist[i] / speed[i]))\n",
    "        # tmp.sort()\n",
    "        counter = Counter(tmp)\n",
    "\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        keys = sorted(counter.keys())\n",
    "        for t in range(n):\n",
    "            if i < len(keys) and counter[keys[i]] > 0 and keys[i] - t > 0:\n",
    "                ans += 1\n",
    "                counter[keys[i]] -= 1\n",
    "                if counter[keys[i]] == 0:\n",
    "                    i += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        t = [(dist[i] - 1) // speed[i] + 1 for i in range(len(dist))]\n",
    "        t.sort()\n",
    "        for i in range(len(t)):\n",
    "            if t[i] < i + 1:\n",
    "                return i\n",
    "        return len(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        import math\n",
    "        length=len(dist)\n",
    "        time=[]\n",
    "        for i in range (0,length):\n",
    "            time.append(math.ceil(dist[i]/speed[i]))\n",
    "        time.sort()\n",
    "        for i in range(0,length):\n",
    "            if time[i]-1-i<0:\n",
    "                return(i)\n",
    "        return(length)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        贪心：每次消灭距离最近且移动速度最快的，尽量存活时间长点\n",
    "        \"\"\"\n",
    "        import math\n",
    "        # 按到达基地需要的分钟数排序，从小到大杀\n",
    "        dist_min = [0] * len(dist)\n",
    "        for i in range(len(dist)):\n",
    "            dist_min[i] = math.ceil(dist[i]/speed[i])\n",
    "        dist_min.sort()\n",
    "\n",
    "        kill_num = 0\n",
    "        minutes = 0\n",
    "        start = 0\n",
    "        while(start <= len(dist_min)-1):\n",
    "            if dist_min[start] > minutes:\n",
    "                kill_num += 1\n",
    "                minutes += 1\n",
    "                start += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return kill_num\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        time = [(dist[i] - 1) // speed[i] for i in range(n)]\n",
    "        time.sort()\n",
    "        for i in range(n):\n",
    "            if time[i] < i:\n",
    "                return i\n",
    "        return n "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        # 每个怪物的最晚可被消灭时间\n",
    "        time = [(dist[i] - 1) // speed[i] for i in range(n)]\n",
    "        time.sort()\n",
    "        for i in range(n):\n",
    "            if time[i] < i:\n",
    "                # 无法消灭该怪物，返回消灭的怪物数量\n",
    "                return i\n",
    "        # 成功消灭全部怪物\n",
    "        return n\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        hitcity=[]\n",
    "        for x in range(len(dist)):\n",
    "            if dist[x] % speed[x] == 0:\n",
    "                hitcity.append(dist[x] // speed[x])\n",
    "            else:\n",
    "                hitcity.append(dist[x] // speed[x] + 1)\n",
    "        hitcity.sort()\n",
    "        print(hitcity)\n",
    "        res = 0\n",
    "        for time in range(len(dist)):\n",
    "            if time < hitcity[time]:\n",
    "                res += 1\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        arrtime = sorted(d/s for d,s in zip(dist,speed))\n",
    "        for i in range(len(dist)):\n",
    "            if arrtime[i] <= i:\n",
    "                return i\n",
    "        \n",
    "        return len(dist)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        time = [(dist[i]-0.1) // speed[i] for i in range(n)]\n",
    "        time.sort()\n",
    "        for i in range(n):\n",
    "            if time[i] < i:\n",
    "                return i\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        avaTime = defaultdict(int)\n",
    "        for d,s in zip(dist, speed):\n",
    "            avaTime[ceil(d/s)] += 1\n",
    "        acc = 0\n",
    "        for t, multi in sorted(avaTime.items()):\n",
    "            if acc+multi > t:\n",
    "                return t\n",
    "            acc += multi\n",
    "        return acc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        a_t = [0 for _ in range(n)]\n",
    "        k_t = [i for i in range(n)]\n",
    "        for i in range(n):\n",
    "            a_t[i] = math.ceil(dist[i] / speed[i])\n",
    "        a_t = sorted(a_t)\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if k_t[i] < a_t[i]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                break\n",
    "        return cnt \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        # 计算每个怪物到达城堡的时间（必须在第x分钟前消灭该怪物，否则会失败）\n",
    "        # 将时间排序\n",
    "        # eta = []\n",
    "        # n = len(dist)\n",
    "        # for i in range(n):\n",
    "        #     eta.append(math.ceil(dist[i] / speed[i]))\n",
    "        # eta.sort()\n",
    "        # for i in range(n):\n",
    "        #     if eta[i] <= i:\n",
    "        #         return i\n",
    "        # return n\n",
    "        \n",
    "        # 前缀和\n",
    "        n = len(dist)\n",
    "        eta = [0] * (n+1) # 第i个时刻，共有多少个怪物会到\n",
    "        for i in range(n):\n",
    "            arr_time = math.ceil(dist[i] / speed[i])\n",
    "            arr_time = min(n, arr_time)\n",
    "            eta[arr_time] += 1\n",
    "        for i in range(1, n+1):\n",
    "            eta[i] = eta[i-1] + eta[i]\n",
    "            if eta[i] > i:\n",
    "                return i\n",
    "        return n\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        # ll = []\n",
    "\n",
    "        # for i in range(len(dist)):\n",
    "        #     ll.append(math.ceil(dist[i] / speed[i]))\n",
    "\n",
    "        # ll.sort()\n",
    "\n",
    "        # for i in range(len(ll)):\n",
    "        #     if ll[i] <= i:\n",
    "        #         return i\n",
    "        # return len(dist)\n",
    "\n",
    "        ll = [0] * (len(dist) + 1)\n",
    "\n",
    "        for i in range(len(dist)):\n",
    "            ll[min(len(dist), math.ceil(dist[i] / speed[i]))] += 1\n",
    "        \n",
    "        zd = 0\n",
    "        for i in range(len(ll)):\n",
    "            if ll[i] > zd:\n",
    "                return i\n",
    "            zd -= ll[i]\n",
    "            zd += 1\n",
    "        return len(dist)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        \"\"\"优化\n",
    "        \n",
    "        Args:\n",
    "            dist: \n",
    "            speed: \n",
    "\n",
    "        Returns:\n",
    "\n",
    "        \"\"\"\n",
    "        num = len(dist)\n",
    "        time2cnt = [0] * (num + 1)  # t时刻到达怪物的数量\n",
    "        for d, s in zip(dist, speed):\n",
    "            t = min((d - 1) // s + 1, num)\n",
    "            time2cnt[t] += 1\n",
    "\n",
    "        cur_cnt = 0\n",
    "        for i, cnt in enumerate(time2cnt):\n",
    "            cur_cnt += cnt\n",
    "            if cur_cnt > i:\n",
    "                return i\n",
    "\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        retVal = 0\n",
    "\n",
    "        arrival = []\n",
    "        for d, s in zip(dist, speed):\n",
    "            arrival.append(d / s)\n",
    "\n",
    "        arrival.sort()\n",
    "\n",
    "        for idx, value in enumerate(arrival):\n",
    "            if value <= idx:\n",
    "                break\n",
    "            retVal += 1\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\r\n",
    "        arrivalTimes = sorted([math.ceil(d/s) for d, s in zip(dist, speed)])\r\n",
    "        for attackTime, arrivalTime in enumerate(arrivalTimes):\r\n",
    "            if arrivalTime <= attackTime: # 來不及消滅\r\n",
    "                return attackTime\r\n",
    "        return len(arrivalTimes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        # 贪心: 排序-->按到达城市时间排序(小--大)\n",
    "        # 每次消灭下一个就会到达城市的怪物\n",
    "\n",
    "        # 这个不行--没道理啊\n",
    "        # z = [d/s for d, s in zip(dist, speed)]\n",
    "        # z.sort()\n",
    "        # print(z)\n",
    "        # for i in range(len(z)):\n",
    "        #     if z[i] <= i:\n",
    "        #         return i\n",
    "        # return len(z)\n",
    "\n",
    "\n",
    "        # 清风python\n",
    "        if not dist:\n",
    "            return 0\n",
    "        \n",
    "        n = len(dist)\n",
    "        for i in range(n):\n",
    "            dist[i] = dist[i] / speed[i]\n",
    "        dist.sort()\n",
    "        for i in range(1, n):\n",
    "            if dist[i] <= i:\n",
    "                return i\n",
    "        return n \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        for i in range(n):\n",
    "            dist[i] = ceil(dist[i]/speed[i])\n",
    "        dist.sort()\n",
    "        for i in range(n):\n",
    "            if dist[i] < i+1:\n",
    "                return i\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        arr = [dist[i]/speed[i] for i in range(n)]\n",
    "        arr.sort()\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if arr[i] <= i:\n",
    "                break\n",
    "            else:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        arr = [dist[i]/speed[i] for i in range(n)]\n",
    "        arr.sort()\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if arr[i] - i<= 0:\n",
    "                break\n",
    "            else:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        ans = 0\n",
    "        times = [(dist[i] - 1) // speed[i] for i in range(n)]\n",
    "        times.sort()\n",
    "        for i, t in enumerate(times):\n",
    "            if t < i:\n",
    "                return i\n",
    "        return len(times)\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n=len(dist)\n",
    "        ans=[[]for _ in range(n)]\n",
    "        # for i,j in zip(dist,speed):\n",
    "        # ans=sorted([math.ceil(i/j) for i,j in zip(dist,speed)])\n",
    "        # count=0\n",
    "        for i in range(n):\n",
    "            ans[i]=math.ceil(dist[i]/speed[i])\n",
    "        ans.sort()\n",
    "        for i,j in enumerate(ans):\n",
    "            if j<=i:\n",
    "                #     count+=1\n",
    "                # else:\n",
    "                return i\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n=len(dist)\n",
    "        ans=[[]for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            ans[i]=math.ceil(dist[i]/speed[i])\n",
    "        count=0\n",
    "        ans.sort()\n",
    "        for i in range(n):\n",
    "            if ans[i]>i:\n",
    "                count+=1\n",
    "            else:\n",
    "                return count\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n=len(dist)\n",
    "        ans=[[]for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            ans[i]=math.ceil(dist[i]/speed[i])\n",
    "        count=0\n",
    "        ans.sort()\n",
    "        for i,j in enumerate(ans):\n",
    "            if j>i:\n",
    "                count+=1\n",
    "            else:\n",
    "                return count\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        steps = []\n",
    "        for d, s in zip(dist, speed):\n",
    "            steps.append(ceil(d / s))\n",
    "        steps.sort()\n",
    "        for idx, step in enumerate(steps):\n",
    "            if idx >= step:\n",
    "                return idx\n",
    "        return idx+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n=len(dist)\n",
    "        ans=[[]for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            ans[i]=math.ceil(dist[i]/speed[i])\n",
    "        count=0\n",
    "        ans.sort()\n",
    "        for i in range(n):\n",
    "            if ans[i]>i:\n",
    "                count+=1\n",
    "            else:\n",
    "                return count\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n=len(dist)\n",
    "        ans=[[]for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            ans[i]=math.ceil(dist[i]/speed[i])\n",
    "        count=0\n",
    "        ans.sort()\n",
    "        for i in range(n):\n",
    "            if ans[i]>i:\n",
    "                count+=1\n",
    "            else:\n",
    "                return count\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n=len(dist)\n",
    "        ans=[[]for _ in range(n)]\n",
    "        # for i,j in zip(dist,speed):\n",
    "        # ans=sorted([math.ceil(i/j) for i,j in zip(dist,speed)])\n",
    "        # count=0\n",
    "        for i in range(n):\n",
    "            ans[i]=math.ceil(dist[i]/speed[i])\n",
    "        ans.sort()\n",
    "        for i,j in enumerate(ans):\n",
    "            if j<=i:\n",
    "                #     count+=1\n",
    "                # else:\n",
    "                return i\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        time=[0 for i in range(0,100005)]\n",
    "        for i in range(0,len(dist)):\n",
    "            tmp = dist[i]//speed[i]\n",
    "            if dist[i]%speed[i]==0:\n",
    "                time[tmp]=time[tmp]+1\n",
    "            else :\n",
    "                time[tmp+1]=time[tmp+1]+1\n",
    "        \n",
    "        pos=1\n",
    "        cnt=0\n",
    "        for i in range(0,len(dist)):\n",
    "            if i>=pos:\n",
    "                return cnt\n",
    "            while time[pos]==0:\n",
    "                pos=pos+1\n",
    "            if(time[pos]):\n",
    "                time[pos]=time[pos]-1\n",
    "                if time[pos]==0:\n",
    "                    pos=pos+1\n",
    "                cnt=cnt+1\n",
    "        return len(dist)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        arrive_time = []\n",
    "        for i in range(len(dist)):\n",
    "            heapq.heappush(arrive_time, dist[i]/speed[i])\n",
    "        count = 0\n",
    "        for i in range(len(dist)):\n",
    "            time = heapq.heappop(arrive_time)\n",
    "            if time <= i:\n",
    "                return count\n",
    "            count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        # for monsterDist, monsterSpeed in zip(dist, speed):\n",
    "        #     print(monsterDist, monsterSpeed, (monsterDist - 1) // monsterSpeed + 1)\n",
    "\n",
    "        arrivalTimes = sorted([monsterDist / monsterSpeed for monsterDist, monsterSpeed in zip(dist, speed)])\n",
    "        print(arrivalTimes)\n",
    "        for attackTime, arrivalTime in enumerate(arrivalTimes):\n",
    "            if arrivalTime <= attackTime:\n",
    "                return attackTime\n",
    "        print(\"rer\", 2 // 6)\n",
    "        return len(arrivalTimes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: list[int], speed: list[int]) -> int:\n",
    "        n = len(dist)\n",
    "        steps = []\n",
    "        for i in range(n):\n",
    "            if dist[i]//speed[i] == 0:\n",
    "                steps.append(1)\n",
    "            elif dist[i]//speed[i] != 0 and dist[i]%speed[i] == 0:\n",
    "                steps.append(dist[i]//speed[i])\n",
    "            else:\n",
    "                steps.append((dist[i]//speed[i])+1)\n",
    "            # count = 0\n",
    "            # while dist[i] > 0:\n",
    "            #     dist[i] -= speed[i]\n",
    "            #     count += 1\n",
    "            # steps.append(count)\n",
    "        heapq.heapify(steps)\n",
    "        # print(steps)\n",
    "        m = 0\n",
    "        while steps:\n",
    "            curr = heapq.heappop(steps)\n",
    "            if curr > m:\n",
    "                m += 1\n",
    "            else:\n",
    "                break\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        import heapq\n",
    "        n = len(dist)\n",
    "        steps = []\n",
    "        for i in range(n):\n",
    "            if dist[i] % speed[i] == 0:\n",
    "                steps.append(dist[i] // speed[i])\n",
    "            else:\n",
    "                steps.append(dist[i] // speed[i] + 1)\n",
    "        heapq.heapify(steps)\n",
    "        # step 0\n",
    "        step = 0\n",
    "        heapq.heappop(steps)\n",
    "        killed = 1\n",
    "        for i in range(n - 1):\n",
    "            step += 1\n",
    "            monster = heapq.heappop(steps)\n",
    "            if monster <= step:\n",
    "                break\n",
    "            killed += 1\n",
    "        return killed\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        t = []\n",
    "        for i in range(n):\n",
    "            tmp = dist[i] // speed[i]\n",
    "            if dist[i]  % speed[i] > 0:\n",
    "                tmp += 1\n",
    "            heapq.heappush(t,tmp)\n",
    "        ans = 0 \n",
    "        # print(t)\n",
    "        while t:\n",
    "            x = heapq.heappop(t)\n",
    "            if ans < x:\n",
    "                ans += 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        time = [math.ceil(dist[i]/speed[i] - 1)  for i in range(len(dist))]\n",
    "        col = {}\n",
    "        for t in time:\n",
    "            if t not in col:\n",
    "                col[t] = 1\n",
    "            else:\n",
    "                col[t] += 1\n",
    "        al = 0\n",
    "\n",
    "        for i in range(max(col.keys()) + 1):\n",
    "            if i not in col:\n",
    "                continue\n",
    "            else:\n",
    "                al += col[i]\n",
    "                if al > i + 1:\n",
    "                    return i +1\n",
    "        return len(dist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        reach_time = [math.ceil(dist[i]/speed[i]) for i in range(n)]\n",
    "        now_time = 0\n",
    "        heapq.heapify(reach_time)\n",
    "        res = 0\n",
    "        while reach_time:\n",
    "            latest = reach_time[0]\n",
    "            heapq.heappop(reach_time)\n",
    "            if now_time < latest:\n",
    "                res += 1\n",
    "            else:\n",
    "                break\n",
    "            now_time += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        dist = [(d-1)//s+1 for d,s in zip(dist,speed)]\n",
    "        hash_ = Counter(dist)\n",
    "        singal = sorted(hash_.keys())\n",
    "        pre = 0\n",
    "        for crt in singal:\n",
    "            hash_[crt] += hash_[pre]\n",
    "            if hash_[crt]>crt: return crt\n",
    "            pre = crt\n",
    "        return len(dist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        dist = [ dist[i]//speed[i] if dist[i]%speed[i]==0 else dist[i]//speed[i]+1 for i in range(len(dist))]\n",
    "        hash_ = Counter(dist)\n",
    "        singal = sorted(hash_.keys())\n",
    "        pre = 0\n",
    "        for crt in singal:\n",
    "            hash_[crt] += hash_[pre]\n",
    "            if hash_[crt]>crt: return crt\n",
    "            pre = crt\n",
    "        return hash_[max(hash_)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        time = [math.ceil(dist[i]/speed[i] - 1)  for i in range(len(dist))]\n",
    "        col = {}\n",
    "        for t in time:\n",
    "            if t not in col:\n",
    "                col[t] = 1\n",
    "            else:\n",
    "                col[t] += 1\n",
    "        al = 0\n",
    "\n",
    "        for k in sorted(col.keys()):\n",
    "            al += col[k]\n",
    "            if al > k + 1:\n",
    "                return k +1\n",
    "        return len(dist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)  # 得出敌人数量\n",
    "        arrive_times = [-(-dist[i]//speed[i]) for i in range(n)]  # 得出敌人到达时间\n",
    "        countdic = {}  # 新建一个新字典\n",
    "        for ar in arrive_times:  # 将到达时间与到达个数存储在字典里\n",
    "            if ar not in countdic:\n",
    "                countdic[ar] = 1\n",
    "            else:\n",
    "                countdic[ar] += 1\n",
    "        arr_en = 0  # 累计已消灭敌人\n",
    "        kill_ene = 0\n",
    "        for i in range(max(countdic.keys()) + 1):  # i为累计可消灭敌人\n",
    "            if i not in countdic.keys():  # 跳过0和空白时间点\n",
    "                continue\n",
    "            else:\n",
    "                if i < countdic[i] + arr_en:  # 判断能消灭的敌人是否小于来到的敌人\n",
    "                    kill_ene = i\n",
    "                    break\n",
    "                arr_en += countdic[i]  # 已被消灭的敌人\n",
    "            kill_ene = arr_en\n",
    "        return kill_ene\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)  # 得出敌人数量\n",
    "        arrive_times = [-(-dist[i]//speed[i]) for i in range(n)]  # 得出敌人到达时间\n",
    "        countdic = {}  # 新建一个新字典\n",
    "        for ar in arrive_times:  # 将到达时间与到达个数存储在字典里\n",
    "            if ar not in countdic:\n",
    "                countdic[ar] = 1\n",
    "            else:\n",
    "                countdic[ar] += 1\n",
    "        arr_en = 0  # 累计已消灭敌人\n",
    "        kill_ene = 0\n",
    "        for i in range(max(countdic.keys()) + 1):  # i为累计可消灭敌人\n",
    "            if i not in countdic.keys():  # 跳过0和空白时间点\n",
    "                continue\n",
    "            else:\n",
    "                if i < countdic[i] + arr_en:  # 判断能消灭的敌人是否小于来到的敌人\n",
    "                    kill_ene = i\n",
    "                    break\n",
    "                arr_en += countdic[i]  # 已被消灭的敌人\n",
    "            kill_ene = arr_en\n",
    "        return kill_ene\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        time = list(map(lambda x, y: x/y,dist, speed))\n",
    "        nb = [i for i in range(len(dist))]\n",
    "        time.sort()\n",
    "        ans = 0\n",
    "        for i,v in enumerate(time):\n",
    "            if v>nb[i]:\n",
    "                ans+=1\n",
    "            else:\n",
    "                return ans\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        tmp = []\n",
    "        for i,j in zip(dist,speed):\n",
    "            if i%j:\n",
    "                tmp.append(i//j+1)\n",
    "            else:\n",
    "                tmp.append(i//j)\n",
    "        \n",
    "        time = list(set(tmp))\n",
    "        time.sort()\n",
    "\n",
    "        cnt = Counter(tmp)\n",
    "\n",
    "        ans = 0\n",
    "        pre = 0\n",
    "        for i in time:\n",
    "            if i - pre < cnt[i]:\n",
    "                ans += i - pre \n",
    "                break\n",
    "            else:\n",
    "                ans += cnt[i]\n",
    "                pre = pre + cnt[i]\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        s = list(range(n))\n",
    "        s.sort(key = lambda x: dist[x]/speed[x])\n",
    "        ans = 1\n",
    "        for i in s[1:]:            \n",
    "            if dist[i] > ans * speed[i]:\n",
    "                ans += 1\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        s = list(range(n))\n",
    "        s.sort(key = lambda x: dist[x]/speed[x])\n",
    "        ans = 1\n",
    "        for i in s[1:]:            \n",
    "            if dist[i] > ans * speed[i]:\n",
    "                ans += 1\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "\n",
    "        def find_left(dived, diving):\n",
    "            if dived % diving:\n",
    "                return dived // diving + 1\n",
    "            return dived // diving\n",
    "\n",
    "        arriving = [find_left(dist[i], speed[i]) for i in range(n)]\n",
    "        arriving.sort(key=lambda vl: -vl)\n",
    "        ans = 0\n",
    "        while arriving and arriving.pop() > ans:\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 贪心 + 排序\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        idxs = [i for i in range(n)]\n",
    "        idxs.sort(key=lambda x: dist[x] / speed[x])\n",
    "        for i, idx in enumerate(idxs):\n",
    "            if i * speed[idx] >= dist[idx]:\n",
    "                return i\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        indices = list(range(n))\n",
    "        indices.sort(key=lambda i: (dist[i] - speed[i]) / speed[i] + 1)\n",
    "        for i in range(n):\n",
    "            j = indices[i]\n",
    "            if dist[j] - i * speed[j] <= 0:\n",
    "                return i\n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(speed)\n",
    "        idxs = sorted(range(n), key = lambda x: dist[x]/speed[x])        \n",
    "        ans = 0\n",
    "        while(True):\n",
    "            if(ans < n and dist[idxs[ans]]/speed[idxs[ans]]>ans):\n",
    "                ans+=1\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)  # 得出敌人数量\n",
    "        arrive_times = [-(-dist[i]//speed[i]) for i in range(n)]  # 得出敌人到达时间\n",
    "        count = [0]*(max(arrive_times)+1)  # 创建一个最长到达的列表\n",
    "        countdic = {}  # 新建一个新字典\n",
    "        for ar in arrive_times:  # 将到达时间与到达个数存储在字典里\n",
    "            if ar not in countdic:\n",
    "                countdic[ar] = 1\n",
    "            else:\n",
    "                countdic[ar] += 1\n",
    "        arr_en = 0  # 累计已消灭敌人\n",
    "        kill_ene = 0\n",
    "        for i in range(max(countdic.keys()) + 1):  # i为累计可消灭敌人\n",
    "            if i not in countdic.keys():  # 跳过0和空白时间点\n",
    "                continue\n",
    "            else:\n",
    "                if i < countdic[i] + arr_en:  # 判断能消灭的敌人是否小于来到的敌人\n",
    "                    kill_ene = i\n",
    "                    break\n",
    "                arr_en += countdic[i]  # 已被消灭的敌人\n",
    "            kill_ene = arr_en\n",
    "        return kill_ene\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(speed)\n",
    "        nums = [dist[i] / speed[i] for i in range(n)]\n",
    "        index = list(range(n))\n",
    "        index.sort(key = lambda x: nums[x])\n",
    "        time = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            idx = index[i]\n",
    "            if dist[idx] > time * speed[idx]:\n",
    "                time += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                break \n",
    "        return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        length=len(speed)\n",
    "        for i in range(length):\n",
    "            if not dist[i]%speed[i]:\n",
    "                speed[i]=dist[i]//speed[i]-1\n",
    "            else:\n",
    "                speed[i]=dist[i]//speed[i]\n",
    "        speed.sort()\n",
    "        for i,j in enumerate(speed):\n",
    "            if j<i:\n",
    "                return i\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        length=len(speed)\n",
    "        for i in range(length):\n",
    "            if not dist[i]%speed[i]:\n",
    "                speed[i]=dist[i]//speed[i]-1\n",
    "            else:\n",
    "                speed[i]=dist[i]//speed[i]\n",
    "        speed.sort()\n",
    "        for i,j in enumerate(speed):\n",
    "            if j<i:\n",
    "                return i\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "      n = len(dist)\n",
    "      for i in range(n):\n",
    "        speed[i] = math.ceil(dist[i] / speed[i])\n",
    "      speed.sort()\n",
    "      for i in range(n):\n",
    "        if speed[i] <= i:\n",
    "          return i\n",
    "      return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        for i in range(len(dist)):\n",
    "            speed[i] = math.ceil(dist[i]/speed[i])\n",
    "        \n",
    "        speed = sorted(speed)\n",
    "        for i in range(len(dist))[:-1]:\n",
    "            speed[i] = speed[i]-i\n",
    "            if speed[i+1]-(i+1)<=0:\n",
    "                return i+1\n",
    "        return len(dist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(dist)\n",
    "        times = [dist[i] / speed[i] for i in range(n)]\n",
    "        times = sorted(times)\n",
    "        time_dict = dict()\n",
    "        for time in times:\n",
    "            if time % 1 == 0:\n",
    "                if int(time-1) in time_dict:\n",
    "                    time_dict[int(time-1)] += 1\n",
    "                else:\n",
    "                    time_dict[int(time-1)] = 1\n",
    "            else:\n",
    "                if int(time) in time_dict:\n",
    "                    time_dict[int(time)] += 1\n",
    "                else:\n",
    "                    time_dict[int(time)] = 1\n",
    "\n",
    "        time_list = list(time_dict.keys())\n",
    "        print(time_dict)\n",
    "        for i in range(len(time_list)):\n",
    "            tmp = time_list[i]+1-ans\n",
    "            num = time_dict[time_list[i]]\n",
    "            if tmp >= num:\n",
    "                ans += num\n",
    "            else:\n",
    "                ans = ans + max(tmp, 1)\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(dist)\n",
    "        times = [dist[i] / speed[i] for i in range(n)]\n",
    "        times = sorted(times)\n",
    "        time_dict = dict()\n",
    "        for time in times:\n",
    "            if time % 1 == 0:\n",
    "                if int(time-1) in time_dict:\n",
    "                    time_dict[int(time-1)] += 1\n",
    "                else:\n",
    "                    time_dict[int(time-1)] = 1\n",
    "            else:\n",
    "                if int(time) in time_dict:\n",
    "                    time_dict[int(time)] += 1\n",
    "                else:\n",
    "                    time_dict[int(time)] = 1\n",
    "\n",
    "        time_list = list(time_dict.keys())\n",
    "        print(time_dict)\n",
    "        for i in range(len(time_list)):\n",
    "            tmp = time_list[i]+1-ans\n",
    "            num = time_dict[time_list[i]]\n",
    "            if tmp >= num:\n",
    "                ans += num\n",
    "            else:\n",
    "                ans = ans + tmp\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        \n",
    "        counter = Counter()\n",
    "        \n",
    "        for i in range(len(dist)):\n",
    "            counter[dist[i] // speed[i] if dist[i] % speed[i] == 0 else dist[i] // speed[i] + 1] += 1\n",
    "        \n",
    "        time = 0\n",
    "        \n",
    "        for key, value in sorted(counter.items()):\n",
    "            if time + value <=  key:\n",
    "                time += value \n",
    "            else:\n",
    "                return key\n",
    "        \n",
    "        return time\n",
    "                \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        c=Counter()\n",
    "        #计算怪物到达城市花费的时间\n",
    "        for x,y in zip(dist,speed):\n",
    "            time=(x+y-1)//y\n",
    "            c[time]+=1\n",
    "        #cur指向下一空闲时间\n",
    "        cur=0\n",
    "        for t,v in sorted(c.items()):\n",
    "            #在时间[cur,t)需要消灭v个怪物+pre\n",
    "            if cur+v<=t:\n",
    "                cur+=v\n",
    "            else:\n",
    "                return t\n",
    "        return cur\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n = len(dist)\n",
    "        def cmp(a, b):\n",
    "            return dist[a]/speed[a]-dist[b]/speed[b]\n",
    "        idx = [i for i in range(n)]\n",
    "        idx.sort(key=functools.cmp_to_key(cmp))\n",
    "        d = 0\n",
    "        for i in range(1,n):\n",
    "            d = dist[idx[i]]//speed[idx[i]]\n",
    "            if (dist[idx[i]]%speed[idx[i]])!=0:\n",
    "                d+=1\n",
    "            if d<=i:\n",
    "                return i\n",
    "                \n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        buf_list = sorted(list(map(lambda x: (x[0]-1)/x[1], list(zip(dist, speed)))))\n",
    "        lenth = len(buf_list)\n",
    "        # print(buf_list)\n",
    "        for i in range(lenth):\n",
    "            if buf_list[i] < i:\n",
    "                return i\n",
    "        return lenth\n",
    "        # print(buf_list)\n",
    "# dist =\n",
    "# [4,2,3]\n",
    "# speed =\n",
    "# [2,1,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        hashmap = {}\n",
    "        for d,s in zip(dist, speed):\n",
    "            if d%s:\n",
    "                time = d//s+1\n",
    "            else:\n",
    "                time = d//s\n",
    "            if time not in hashmap:\n",
    "                hashmap[time] = 0\n",
    "            hashmap[time] += 1\n",
    "        prev = 0\n",
    "        total = 0\n",
    "        available_shot = 0\n",
    "        print(sorted(hashmap.items(), key=lambda x:x[0]))\n",
    "        for step, val in sorted(hashmap.items(), key=lambda x:x[0]):\n",
    "            \n",
    "            available_shot += step-prev\n",
    "            available_shot_after = available_shot - val\n",
    "            # print(total, available_shot, available_shot_after)\n",
    "            if available_shot_after<0:\n",
    "                return total + available_shot\n",
    "            total += val\n",
    "            prev = step\n",
    "            available_shot = available_shot_after\n",
    "        return total\n",
    "  \n",
    "    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        # 贪心\n",
    "        t=[]\n",
    "        for d,s in zip(dist,speed):\n",
    "            t.append((d+s-1)//s)\n",
    "        freqs=Counter(t)\n",
    "        # print(freqs)\n",
    "        freqs=sorted(freqs.items(),key=lambda x:x[0])\n",
    "        cnt=0\n",
    "        for t,f in freqs:\n",
    "            cnt+=f\n",
    "            if t<cnt:\n",
    "                return t\n",
    "        return len(dist)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        n=len(dist)\n",
    "        ans=[[]for _ in range(n)]\n",
    "        # for i,j in zip(dist,speed):\n",
    "        # ans=sorted([i/j for i,j in zip(dist,speed)])\n",
    "        # count=0\n",
    "        for i in range(n):\n",
    "            ans[i]=dist[i]/speed[i]\n",
    "        ans.sort()\n",
    "        for i,j in enumerate(ans):\n",
    "            if j<=i:\n",
    "                #     count+=1\n",
    "                # else:\n",
    "                return i\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:\n",
    "        can = [ii // jj if ii % jj else ii // jj - 1 for ii, jj in zip(dist, speed)]\n",
    "        res, idx = 0, 0\n",
    "        for k, v in sorted(Counter(can).items(), key=lambda i:i[0]):\n",
    "            if k - idx >= v - 1:\n",
    "                res += v\n",
    "                idx += v\n",
    "            else:\n",
    "                res += (k - idx + 1)\n",
    "                break\n",
    "        return res\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
